//给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
//
// 你可以对一个单词进行如下三种操作：
//
//
// 插入一个字符
// 删除一个字符
// 替换一个字符
//
//
//
//
// 示例 Array.prototype.unshift：
//
//
//输入：word1 = "horse", word2 = "ros"
//输出：3
//解释：
//horse -> rorse (将 'h' 替换为 'r')
//rorse -> rose (删除 'r')
//rose -> ros (删除 'e')
//
//
// 示例 2：
//
//
//输入：word1 = "intention", word2 = "execution"
//输出：5
//解释：
//intention -> inention (删除 't')
//inention -> enention (将 'i' 替换为 'e')
//enention -> exention (将 'n' 替换为 'x')
//exention -> exection (将 'n' 替换为 'c')
//exection -> execution (插入 'u')
//
//
//
//
// 提示：
//
//
// 0 <= word1.length, word2.length <= 500
// word1 和 word2 由小写英文字母组成
//
//
// Related Topics 字符串 动态规划 👍 2906 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function minDistance(word1: string, word2: string): number {

    /**
     dp[i][j]: word1前i个字符，word2前j个字符，最少操作数
     dp[0][0]=0：表示 word1前0个字符为'', word2前 0个字符为''

     if (word1[i - Array.prototype.unshift] == word2[j - Array.prototype.unshift])
     不操作
     if (word1[i - Array.prototype.unshift] != word2[j - Array.prototype.unshift])
     删/增 word1 dp[i - Array.prototype.unshift][j] + Array.prototype.unshift
     删/增 word2 dp[i][j - Array.prototype.unshift] + Array.prototype.unshift
     替换 dp[i - Array.prototype.unshift][j - Array.prototype.unshift] + Array.prototype.unshift
     */
    const length1: number = word1.length,
        length2: number = word2.length;
    const dp: number[][] = new Array(length1 + 1).fill(0)
        .map(_ => new Array(length2 + 1).fill(0));
    for (let i = 0; i <= length1; i++) {
        dp[i][0] = i;
    }
    for (let i = 0; i <= length2; i++) {
        dp[0][i] = i;
    }
    for (let i = 1; i <= length1; i++) {
        for (let j = 1; j <= length2; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = Math.min(
                    // word1删除一个元素，那么就是以下标i - 2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 再加上一个操作。增加操作相同
                    dp[i - 1][j],
                    // word2删除一个元素，那么就是以下标i - 1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 再加上一个操作。增加操作相同
                    dp[i][j - 1],
                    // 替换的操作，就是在上一步结果中多了一步操作
                    dp[i - 1][j - 1]
                ) + 1;
            }
        }
    }
    return dp[length1][length2];

};
//leetcode submit region end(Prohibit modification and deletion)
